#include <queue>
#include <vector>
#include <list>

#include "cover.h"

using std::vector;
using std::list;
using std::priority_queue;

/**
 * private comparison predicate object used by the priority_queue in 
 * greedy_vc2. Compares integers by treating them as row indices and 
 * comparing the corresponding rowsums. Needs an array of row sums 
 * to compare with, hence the lack of a default constructor.
 */
class rowsum_cmp_t
{
    private:
	/**
	 * pointer to array of rowsums
	 */
	int * _rowsums;

    public:
	// no default constructor b/c argument is mandatory

	/**
	 * @param   rowsums	a rowsums matrix
	 */
	rowsum_cmp_t (int * rowsums) : _rowsums(rowsums) {}

	/**
	 * Compares by rowsums using arguments as indices. Does not check
	 * index bounds, so assumes input indices are valid.
	 * @param   i	index of first row
	 * @param   j	index of second row
	 * @return  true if rowsum of row i is less than rowsum of row j
	 */
	bool operator()(int i, int j) {
	    return _rowsums[i] < _rowsums[j];
	}
};

/**
 * Improved greedy algorithm based on VERTEX COVER 2
 * Modifies: matrix, cover, solutions
 *
 * @param   matrix	the 0,1 matrix represented as vector of vectors of int
 * @param   ncols   	number of data columns representing lines,
 *		    	not number of characters
 * @param   nrows   	number of rows
 * @param   cover   	int array of length ncols
 * @param   solutions	a storage container for solution row indices
 */
void greedy_vc2 (
	vector<vector<int> > &matrix,
	int nrows,
	int ncols,
	int *cover,
	list<int> &solutions
	)
{
    /**
     * Algorithm description
     *
     * while not finished covering
     *. count the number of 1's in each column
     *. find the uncovered column with smallest column sum
     *. save all indices of rows rovering that column 
     *  (i.e. containing a 1 in that column) temporarily 
     *
     *. while saved rows remain
     *   - choose the row with the greatest rowsum
     *	 - if the row covers an *uncovered* column
     *	    - add the row to the solution set
     *	    - cover the matrix with that row
     *	 - remove the row from set of saved rows
     *
     * The point of this algorithm is to eliminate the selection of redundant
     * rows (vertices) by ensuring each selected row *strictly* increases the
     * number of covered columns. It was designed to work with general set
     * cover so it consequently works with vertex and segment cover as well.
     */


    int *colsums = new int[ncols];
    int *rowsums = new int[nrows];

    // initialize colsums to all 0's
    //for (int *ptr = colsums + (ncols-1); ptr >= colsums; --ptr ) { *ptr = 0; }
    for (int i=0; i < ncols; ++i) { colsums[i] = 0;}

    /* initialize rowsums: count the 1's in each row;  at the same time,
     * initialize colsums: count the 1's in each column */
    int * row = rowsums;
    vector<vector<int> >::iterator rowvi = matrix.begin();
    vector<vector<int> >::iterator rowendi = matrix.end();
    while (rowvi != rowendi) {
	int rowcount = 0;
	int endcol = rowvi->size();
	for (int j = 0; j< endcol; j++) {
	    int bit = rowvi->at(j);
	    rowcount += bit;
	    colsums[j] += bit;
	}
	*row = rowcount;
	++row; ++rowvi;
    }

    while ( !finished(cover, ncols) ) {
	// find min col that has NOT been covered yet
	// !finished() guarantees one exists
	int colj, mincolj;
	colj = mincolj = 0;
	while (colj < ncols) {
	    if ( (cover[mincolj] == 1) || // if mincolj is covered, advance it
		    (cover[colj] != 1) && (colsums[mincolj] > colsums[colj]) )
	    {
		mincolj = colj;
	    }
	    ++colj;
	}
	// POST: mincolj == index of minimum uncovered column sum

	rowsum_cmp_t rowsum_less(rowsums);  // "less than" predicate object

	/* temporary storage for rows to cover
	 * use a priority queue since we want them ordered by row sum */
	priority_queue<int, vector<int>, rowsum_cmp_t > row_indices(rowsum_less);

	int endrow = matrix.size();
	for (int i=0; i<endrow; i++) {	// for all rows i ...
	    if ( matrix.at(i).at(mincolj) == 1 ) { //  ... with a 1 in mincol
		row_indices.push(i);	// save it for covering later
		// if we cover matrix here, all other 1's in the column are lost
		// so we save all the row indices first
	    }
	}

	while (!row_indices.empty()){ // while saved rows remain ...
	    int i = row_indices.top(); // get the row index with greatest row sum
	    row_indices.pop();
	    vector<int> &row = matrix.at(i); // get the actual row vector
	    for (int j=0; j<ncols; j++) {   // for all columns in the row
		// if row covers an uncovered column
		if ( (row.at(j) == 1) && (cover[j] != 1) ) {
		    solutions.push_back(i);	// add it to solution set
		    cover_with_row (matrix, i, cover, rowsums, colsums);
		    break;			// end for loop
		}
	    }
	}
    }

    /* clean up duty -- free up memory */
    delete[] colsums;
    delete[] rowsums;
}

